package com.learn.algorithm.dynamic.programming;

public class LeetCode97 {
    // dp[i][j] s1[...i] s2[...j]能否交错拼接出s3[...i+j]

    public static boolean isInterleave(String str1, String str2, String str3) {
        int n = str1.length();
        int m = str2.length();
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        char[] s3 = str3.toCharArray();
        if (s1.length + s2.length != s3.length) {
            return false;
        }
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        // s2 == ""时
        for (int i = 1; i <= n; i++) {
            if (s1[i - 1] != s3[i - 1]) {
                break;
            }
            dp[i][0] = true;
        }
        // s1 == ""时
        for (int j = 1; j <= m; j++) {
            if (s2[j - 1] != s3[j - 1 ]) {
                break;
            }
            dp[0][j] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);
            }
        }

        return dp[n][m];
    }
}
